﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using GraphosData;

namespace GraphosControls
{
    class SearchEngine
    {
        private const int PARTIAL_MATCH_THRESH = 3;

        private IList<Node> data;
        private Node partialMatch = null;

        public Node PartialMatch
        {
            get { return partialMatch; }
        }
    
        public SearchEngine(IList<Node> data)
        {
            this.data = data;
        }

        public List<Node> Search(String strFind)
        {
            if (strFind == null)
                throw new NullReferenceException();

            strFind = strFind.Trim();
            if (strFind.Length == 0)
                return null;

            int min = 999999, dist;
            Node myPartial = null;
            SortedList<String, Node> frontResults = new SortedList<String, Node> ();
            SortedList<String, Node> midResults = new SortedList<String, Node>();
            SortedList<String, Node> backResults = new SortedList<String, Node> ();
            char[] delims = { ' ' };
            strFind = strFind.ToLower();
            String[] terms = strFind.Split(delims);
       
            foreach(Node n in data)
            {
                addSearchItem(n, terms, frontResults, midResults, backResults);
                dist = LevenshteinDistance(strFind, n.Person.FirstName);
                if (dist < min)
                {
                    myPartial = n;
                    min = dist;
                }
            }

            dist = LevenshteinDistance(strFind, myPartial.Person.FirstName);
            if (strFind.Length > 3 && myPartial != null &&
                dist < 3 + strFind.Length / 6)
            {
                partialMatch = myPartial;
            }
            else
            {
                partialMatch = null;
            }

            List<Node> results = new List<Node>();
            results.AddRange(frontResults.Values.ToArray<Node>());
            results.AddRange(midResults.Values.ToArray<Node>());
            results.AddRange(backResults.Values.ToArray<Node>());

            return results;
        }

        private int LevenshteinDistance(String s, String t)
        {
            int m = s.Length, n = t.Length;
            int cost;
            int[,] d = new int[m + 1, n + 1];

            for (int i = 0; i < m + 1; i++)
                d[i, 0] = i;
            for (int j = 0; j < n + 1; j++)
                d[0, j] = j;

            for (int i = 1; i < m + 1; i++)
            {
                for (int j = 1; j < n + 1; j++)
                {
                    if (s[i - 1] == t[j - 1])
                        cost = 0;
                    else
                        cost = 1;

                    d[i, j] = min(d[i - 1, j] + 1,
                                  d[i, j - 1] + 1,
                                  d[i - 1, j - 1] + cost);
                }
            }

            return d[m, n];
        }

        private int min(int a, int b, int c)
        {
            int min = a;
            if (b < min)
                min = b;
            if (c < min)
                min = c;
            return min;
        }

        private void addSearchItem(Node n, String[] terms, SortedList<String, Node> frontResults, 
                        SortedList<String, Node> midResults, SortedList<String, Node> backResults)
        {
            String first = n.Person.FirstName.ToLower();
            String last = n.Person.LastName.ToLower();

            //insert each name only once
            if (frontResults.ContainsKey(first + last) ||
                    midResults.ContainsKey(first + last) ||
                    backResults.ContainsKey(first + last))
                return;

            if (terms.Length == 1)
            {
                if (first.StartsWith(terms[0]))
                    frontResults.Add(first + last, n);
                else if (last.StartsWith(terms[0]))
                    midResults.Add(first + last, n);
                else if (Regex.IsMatch(first, terms[0] + ".*"))
                    backResults.Add(first + last, n);
                else if (Regex.IsMatch(last, terms[0] + ".*"))
                    backResults.Add(first + last, n);
            }

            if (terms.Length == 2)
            {
                if (first.Equals(terms[0]) && last.StartsWith(terms[1]))
                    frontResults.Add(first + last, n);
                else if (first.StartsWith(terms[0]) && last.StartsWith(terms[1]))
                    midResults.Add(first + last, n);
                else if (Regex.IsMatch(first, terms[0] + ".*") && last.StartsWith(terms[1]))
                    backResults.Add(first + last, n);
                else if (Regex.IsMatch(first, terms[0] + ".*") && Regex.IsMatch(last, ".*" + terms[0] + ".*"))
                    backResults.Add(first + last, n);
            }
        }
    }
}
